/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/implement-trie-prefix-tree
   @Language: C++
   @Datetime: 16-02-09 05:53
   */

class Trie {
	struct TrieNode{
		static const int SIZE=26;
		TrieNode * child[SIZE+1];   // child[SIZE]='\0'
		TrieNode(){
			for(int i=0; i<=SIZE; child[i++]=NULL);
		}
		~TrieNode(){
			for(int i=0; i<=SIZE; ++i)
				if (child[i]) delete child[i];
		}
	};
	TrieNode *root=NULL;
public:
	Trie() {
		// do intialization if necessary
		root=new TrieNode();
	}
	~Trie(){
		if(root) delete root;
	}

	/*
	 * @param word: a word
	 * @return: nothing
	 */
	void insert(string &word) {
		// write your code here
		if(word.length()<1) return;
		TrieNode *node=root;
		for(int i=0; i<word.length(); node=node->child[word[i]-'a'], ++i)
			if(node->child[word[i]-'a']==NULL)
				node->child[word[i]-'a']=new TrieNode();
		if(node->child[TrieNode::SIZE]==NULL)   // '\0'
			node->child[TrieNode::SIZE]=new TrieNode();
	}

	/*
	 * @param word: A string
	 * @return: if the word is in the trie.
	 */
	bool search(string &word) {
		// write your code here
		TrieNode *node=root;
		for(int i=0; i<word.length(); ++i){
			node=node->child[word[i]-'a'];
			if(node==NULL) return false;
		}
		return node->child[TrieNode::SIZE];
	}

	/*
	 * @param prefix: A string
	 * @return: if there is any word in the trie that starts with the given prefix.
	 */
	bool startsWith(string &prefix) {
		// write your code here
		TrieNode *node=root;
		for(int i=0; i<prefix.length(); ++i){
			node=node->child[prefix[i]-'a'];
			if(node==NULL) return false;
		}
		return true;
	}
};
